public class Solution {

private int rows;
private int columns;
private bool[,] visited;

private Trie trie;
private HashSet<string> allInputWords;
private HashSet<string> results;

public IList<string> FindWords(char[,] board, string[] words) {
    
    // init words hashset and trie
    trie = new Trie();
    allInputWords = new HashSet<string>();
    foreach (string str in words)
    {
        allInputWords.Add(str);
        trie.Insert(str);
    }
    
    rows = board.GetLength(0);
    columns = board.GetLength(1);
    
    results = new HashSet<string>();
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < columns; j++)
        {
            visited = new bool[rows, columns];
            Search(board, "", i, j);
        }
    }
    
    return results.ToList();
}

private void Search(char[,] board, string prefix, int i, int j)
{
    if (i < 0 || i >= rows || j < 0 || j >= columns || visited[i, j]) return;
    
    prefix += board[i, j].ToString();
    
    // not our target word preifx, quit.
    if (!trie.StartsWith(prefix)) return;
    
    // found an exact match, add to result
    if (allInputWords.Contains(prefix)) results.Add(prefix);
    
    // continue search
    visited[i, j] = true;
    Search(board, prefix, i, j + 1);
    Search(board, prefix, i - 1, j);
    Search(board, prefix, i + 1, j);
    Search(board, prefix, i, j - 1);
    visited[i, j] = false;
    
    return;
}
